Kandidatnummer: 10001 og 10146
from graph_utils.graph import Graph, nx, plt
from graph_utils.grid_graph import GridGraph
from graph_utils.constructed_graph import ConstructedGraph
from graph_utils.watts_strogatz import WattsStrogatz
from graph_utils.barabasi_albert import BarabasiAlbert
from graph_utils.real_network_graph import RealNetworkGraph
from graph_utils.vdes_graph import VDESGraph
import matplotlib
import numpy as np
import operator
import matplotlib.pyplot as plt
I denne delen skal vi bli kjent med hvordan man plotter grafer.
Lag en graf ved å først opprette et objekt av klassen Graph. Legg deretter til 5-10 noder ved å bruke metoden add_node() eller add_nodes_from(). Legg så til kanter mellom de nodene du ønsker ved å bruke add_edge() eller add_edges_from(). Bruk til slutt metoden draw() for å tegne grafen.
graf = Graph(seed=1234)
graf.add_node(1)
graf.add_nodes_from([2,3,4,5,6])
graf.add_edge(1,2)
graf.add_edges_from([(1,3),(1,4),(2,5),(4,6),(3,6),(4,5)])
graf.draw()
Man kan finne antall noder ved å bruke metoden number_of_nodes(). Prøv den ut på grafobjektet du opprettet i forrige oppgave og print resultatet.
print(graf.number_of_nodes())
6
På samme måte som med noder kan man finne antallet kanter i grafen med metoden number_of_edges(). Bruk den på grafen fra oppgave 1.1 til å finne antall kanter i grafen og print resultatet.
print(graf.number_of_edges())
7
Opprett et GridGraph-objekt med 5 x 5 noder. Tegn korteste vei mellom node (4, 4) og (1, 2) med metoden mark_shortest_path().
grid = GridGraph(5,5)
grid.mark_shortest_path((4, 4),(1,2))
Vi skal forsette å bruke grafen fra forrige oppgave. Fjern node (1, 3) og (2, 2) ved å bruke metoden remove_node(). Finn nå korteste vei mellom node (4, 4) og (1, 2) og tegn resultatet. (Merk at nodene ikke nødvendigvis blir tegnet på samme steder som i forrige oppgave, men den tegner en isomorf graf)
grid.remove_node((1,3))
grid.remove_node((2,2))
grid.mark_shortest_path((4, 4),(1,2))
Hvor mange noder må minst slettes for at korteste vei mellom node (4, 4) og (1, 2) skal bli lenger enn den var i oppgave 1.5, men at det fremdeles finnes en vei?
grid.remove_node((3,1))
grid.remove_node((3,4))
grid.mark_shortest_path((4, 4),(1,2))
Hvor mange noder må slettes for at det ikke skal eksistere noen vei mellom node (4, 4) og (1, 2), med utgangspunkt i grafen slik den er i oppgave 1.5?
# Kodecelle hvis du vil teste
Opprett et WattsStrogatz-objekt med parametre n=100, k=4 og p=0.1.
Tegn så grafen, og finn korteste vei mellom node 53 og 75.
ws1 = WattsStrogatz(n=100, k=4, p=0.1, seed=69)
ws1.draw()
ws1.mark_shortest_path(53,73)
Lag følgende 4 grafer, alle med 100 noder:
Du trenger ikke tegne grafene, bare opprett et objekt for hver graf. Det kan likevel være lurt å tegne grafen for din egen del, så du vet hvordan den ser ut.
ba1 = BarabasiAlbert(n=100, m=1)
ba2 = BarabasiAlbert(n=100, m=2, seed=ba1.seed)
ws2 = WattsStrogatz(n=100, k=2, p=0.1, seed=69)
ws3 = ws1
For hver av de fire grafene: lag et histogram som viser degree distribution.
histogram() for å gjøre dette. ba1.histogram()
[0, 64, 16, 8, 6, 2, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 1]
ba2.histogram()
[0, 0, 50, 15, 12, 2, 6, 7, 1, 3, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
ws2.histogram()
[0, 9, 82, 9]
ws3.histogram()
[0, 0, 1, 12, 74, 12, 1]
Kommenter resultatene med hensyn på sårbarheter for hver av de 4 grafene i forrige oppgave.
Hvordan endrer degree distribution seg for en Barabasi Albert graf seg når m øker fra 1 til 2? Forklar hvorfor.
Hvordan endrer degree distribution seg for en Watts Strogats graf seg når k øker fra 2 til 4? Forklar hvorfor.
Hvordan endrer degree distribution seg for en Watts Strogats graf dersom p øker? Test det ut og forklar hvorfor.
# Eventuell kode her
Hva sier degree distribution om nettverket?
# Assume the task is about the graphs in task 2.1
myGraf1 = ba1.closeness_centrality()
myGraf2 = ba2.closeness_centrality()
graft1High = []
graft2High = []
print("\n-- graf 1 --\nNode: Verdi")
# graf 1
for x in range(0,5):
k = max(myGraf1.items(), key=operator.itemgetter(1))[0]
graft1High.append(k)
v = max(myGraf1.items(), key=operator.itemgetter(1))[1]
print (k," : ", v)
del myGraf1[k]
print("\n-- graf 2 --\nNode: Verdi")
# graf 2
for x in range(0,5):
k = max(myGraf2.items(), key=operator.itemgetter(1))[0]
graft2High.append(k)
v = max(myGraf2.items(), key=operator.itemgetter(1))[1]
print (k," : ", v)
del myGraf2[k]
kommentar = "\ncloseness_centrality er summen av kortest vei fra en node til alle andre noder, dvs. at de spiller en sentral rolle der en node A ofte må innom (en eller flere) av disse 5 for korteste vei til en node B"
print(kommentar)
ba1.mark_nodes(graft1High)
ba2.mark_nodes(graft2High)
-- graf 1 -- Node: Verdi 1 : 0.3944223107569721 0 : 0.34494773519163763 5 : 0.33559322033898303 6 : 0.2990936555891239 23 : 0.29376854599406527 -- graf 2 -- Node: Verdi 3 : 0.49748743718592964 2 : 0.495 7 : 0.44 1 : 0.4125 12 : 0.4074074074074074 closeness_centrality er summen av kortest vei fra en node til alle andre noder, dvs. at de spiller en sentral rolle der en node A ofte på innom (en eller flere) av disse 5 for korteste vei til en node B
For graf 4: Identifiser noder som har høy verdi av en indeks, men lav av en annen indeks. Tips: tegning illustreringen av centrality indexene for å se det ut ifra grafen. Hva blir konsekvensene dersom disse nodene feiler?
ws3.draw_closeness_centrality(1137)
ws3.draw_betweenness_centrality(1137)
ws3.draw_degree_centrality(1137)
# Node 19 og 7 har f.eks ganske høy betweenness og lav degree, som betyr at det er mange av
# grafens "korteste veier" som går via 19 og 7, men at de ikke har så mange kanter tilknyttet andre noder
# følgelig kan vi påstå at nettverket vil få ganske redusert ytelse dersom en av disse feiler
Konstruer et nettverk bestående av mellom 9 og 15 noder med en node som har høyest closeness centrality, og en av de laveste degree centrality verdiene. Tips: Siden grafen ikke er så stor kan det være lettere å hardkode noder og edges enn å generere de ved hjelp av en for loop.
networkGraph = Graph(seed=69420)
networkGraph.add_nodes_from([1,2,3,4,5,6,7,8,9])
networkGraph.add_edges_from([(5,4),(5,6),(4,3),(3,2),(2,1),(1,4),(6,7),(7,8),(8,9),(9,6)])
closeNetwork = networkGraph.closeness_centrality()
degreeNetwork = networkGraph.degree_centrality()
k1 = max(closeNetwork.items(), key=operator.itemgetter(1))[0]
v1 = max(closeNetwork.items(), key=operator.itemgetter(1))[1]
v2 = min(degreeNetwork.items(), key=operator.itemgetter(1))[1]
def findMinDegree():
minDegree = {}
for x in degreeNetwork:
if degreeNetwork[x] == v2:
minDegree[x] = degreeNetwork[x]
print("lowest degree:\n",minDegree)
findMinDegree()
print("\nCloseness\n",k1,":",v1)
print("\n- Vi kan se at node 5 har størst closeness centrality, og delt laveste degree centrality verdiene -")
lowest degree:
{1: 0.25, 2: 0.25, 3: 0.25, 5: 0.25, 7: 0.25, 8: 0.25, 9: 0.25}
Closeness
5 : 0.5
- Vi kan se at node 5 har størst closeness centrality, og delt laveste degree centrality verdiene -
Her skal vi analysere og diskutere reelle/ simulerte nettverk.
I denne oppgaven skal vi analysere Uninett sitt nettverk slik det var i 2011. Klassen RealNetworkGraph tar inn en url av en fil med filtypen .graphml. Lag et objekt for kjernenettet i Norge og tegn det. Filene som kan analyseres finnes på nettsiden Topology Zoo.
# Assuming we have to ctrl + F for uninett and copy link location for the 2011 result (graphml).
# Yielding this link: http://www.topology-zoo.org/files/Uninett2011.graphml
core_network = RealNetworkGraph("http://www.topology-zoo.org/files/Uninett2011.graphml")
core_network.draw()
Plot et histogram over degree distribution for nettverket til Uninett
core_network.histogram()
[0, 11, 30, 12, 7, 2, 4, 1, 2]
For hver av de tre centrality indeksene, print gjennomsnittlig centrality i nettverket til Uninett.
# Declaring the three centrality indexes mentioned in the lecure. Returns key/value pairs for each node
cn_close = core_network.closeness_centrality()
cn_between = core_network.betweenness_centrality()
cn_degree = core_network.degree_centrality()
def average(g):
total = 0
# Loop through nodes, find avg of the values
for key in g:
total += g[key]
return total/len(g)
print(f"Average closeness: {round(average(cn_close), 3)}")
print(f"Average betweenness: {round(average(cn_between), 3)}")
print(f"Average degree: {round(average(cn_degree), 3)}")
Average closeness: 0.244 Average betweenness: 0.049 Average degree: 0.041
Diskuter resultatene fra oppgave 3.2 og 3.3. Er nettverket robust? Forklar.
Hvilket av nettverkene fra del 2 ligner Uninett sitt mest på?
Constructed graph simulerer et reelt netverk. Den består av et kjernenett med en grid struktur, et regionalnett og et tettbebyggd aksessnett. Bruk klassen ConstructedGraph og tegn så grafen.
constructedGraph = ConstructedGraph()
constructedGraph.draw()
Illustrer på grafen verdien av de tre centrality indeksene. Tips: bruk de metodene som er ferdiglagde.
print("Based on degree centrality: ")
constructedGraph.draw_degree_centrality(avg_size=700)
print("Based on closeness centrality: ")
constructedGraph.draw_closeness_centrality(avg_size=700)
print("Based on betweenness centrality: ")
constructedGraph.draw_betweenness_centrality(avg_size=700)
# Det viser seg at det hender maskinen printer alt før grafene blir tegnet, men da ser man i hvert fall rekkefølgen
Based on degree centrality: Based on closeness centrality: Based on betweenness centrality:
Diskuter viktigheten og robustheten til regionalnettet.
Bruk objektet i denne oppgaven. Grafen er et utsnitt av et VDES nettverk i aksjon der båtene snakker med hverandre, satelittene og de landbaserte radiotårnene.
VDES = VDESGraph()
VDES.draw()
For å vite hvor vi skal angripe er det en fordel å vite hvor vi kan gjøre mest mulig skade. Bruk de numeriske verdiene for de forskjellige centrality målene du lærte i de tidligere delene for ut hvilken node som er den viktigste i nettverket.
closenessVDES = VDES.closeness_centrality()
degreeVDES = VDES.degree_centrality()
betweenessVDES = VDES.betweenness_centrality()
# Hjelpemetoder for å finne høyeste verdi (og hvis det er flere med like verdier, finne alle)
def findMaxDegree():
maxDegree = {}
v2 = max(degreeVDES.items(), key=operator.itemgetter(1))[1]
for x in degreeVDES:
if degreeVDES[x] == v2:
maxDegree[x] = degreeVDES[x]
print("\nhighest degree:\n",maxDegree)
def findMaxClosenness():
maxClosenness = {}
v1 = max(closenessVDES.items(), key=operator.itemgetter(1))[1]
for x in closenessVDES:
if closenessVDES[x] == v1:
maxClosenness[x] = closenessVDES[x]
print("\nhighest closeness:\n",maxClosenness)
def findMaxbetweeness():
maxBetweeness = {}
v3 = max(betweenessVDES.items(), key=operator.itemgetter(1))[1]
for x in betweenessVDES:
if betweenessVDES[x] == v3:
maxBetweeness[x] = betweenessVDES[x]
print("\nhighest betweeness:\n",maxBetweeness)
# for å enkelt kunne kalle alle på en gang
def findAllMaxCategories():
findMaxDegree()
findMaxClosenness()
findMaxbetweeness()
findAllMaxCategories()
print("\n- Vi ser at 'satalite1' er har høyest verdi på alle centrality målene -")
highest degree:
{'boat0': 0.38461538461538464, 'boat3': 0.38461538461538464, 'boat4': 0.38461538461538464, 'satilite1': 0.38461538461538464, 'radio_tower0': 0.38461538461538464}
highest closeness:
{'satilite1': 0.6190476190476191}
highest betweeness:
{'satilite1': 0.3496947496947496}
- Vi ser at 'satalite1' er har høyest verdi på alle centrality målene -
VDES.draw_betweenness_centrality(avg_size=3000)
VDES.draw_closeness_centrality(avg_size=3000)
VDES.draw_degree_centrality(avg_size=3000)
Analyser nettverket med degree distribution og kanter per node. Diskuter robustheten bassert på de nevnte målene.
VDES.histogram()
[0, 1, 2, 4, 2, 5]
Random metoden her er seedet, altså vil den gi ut samme random hver gang.
attackVDES = VDES.delete_random_nodes(1, print_result=True)
attackVDES.draw()
attackVDESrandom = VDES.delete_random_nodes(3, print_result=True)
attackVDESrandom.draw()
Removed node boat6 using random_fault
Removed node boat6 using random_fault Removed node satilite1 using random_fault Removed node boat9 using random_fault
Utfør ett enkelt målrettet angrep. Velg her den metoden som gjør mest skade og begrunn hvorfor.
attackRandomVDES = VDES.delete_nodes_attack(n=1, centrality_index="closeness", print_result=True)
print("- Fra oppg 4.1.1, får vi at Satalite1 har høyest verdi i alle kategoriene og vi utgjør dermed mest skade ved å angripe denne -")
attackVDES.draw()
Removed node satilite1 using closeness_centrality - Fra oppg 4.1.1, får vi at Satalite1 har høyest verdi i alle kategoriene og vi utgjør dermed mest skade ved å angripe denne -
Utfør 3 angrep totalt og utfør mest mulig skade. Sammenlign med like mange tilfeldige feil og forklar resultatet.
# attack 1
# vi har gjort utregning for mest skade ved første node i oppgaven over
print("\n- Angrep 1 -")
attackVDES = VDES.delete_nodes_attack(n=1, centrality_index="closeness", print_result=True)
attackVDES.draw()
# attack 2
closenessVDES = attackVDES.closeness_centrality()
degreeVDES = attackVDES.degree_centrality()
betweenessVDES = attackVDES.betweenness_centrality()
print("- Angrep 2 -")
findAllMaxCategories()
print("\nser at båt 4 skårer høyest på degree og closeness")
attackVDES2 = attackVDES.delete_nodes_attack(n=1, centrality_index="closeness", print_result=True)
attackVDES2.draw()
# attack 3
closenessVDES = attackVDES2.closeness_centrality()
degreeVDES = attackVDES2.degree_centrality()
betweenessVDES = attackVDES2.betweenness_centrality()
print("- Angrep 3 -")
findAllMaxCategories()
print("\nser at båt 0 skårer høyest på alle kategorier")
attackVDES3 = attackVDES2.delete_nodes_attack(n=1, centrality_index="closeness", print_result=True)
attackVDES3.draw()
# after attack 3
closenessVDES = attackVDES3.closeness_centrality()
degreeVDES = attackVDES3.degree_centrality()
betweenessVDES = attackVDES3.betweenness_centrality()
print("- Resultat etter angrep 3 -")
findAllMaxCategories()
# attack random nodes
closenessVDES = attackRandomVDES.closeness_centrality()
degreeVDES = attackRandomVDES.degree_centrality()
betweenessVDES = attackRandomVDES.betweenness_centrality()
print("\n\n- Random angrep -")
findAllMaxCategories()
- Angrep 1 - Removed node satilite1 using closeness_centrality
- Angrep 2 -
highest degree:
{'boat4': 0.41666666666666663, 'radio_tower0': 0.41666666666666663}
highest closeness:
{'boat4': 0.5041666666666667}
highest betweeness:
{'boat6': 0.2840909090909091}
ser at båt 4 skårer høyest på degree og closeness
Removed node boat4 using closeness_centrality
- Angrep 3 -
highest degree:
{'boat0': 0.36363636363636365, 'boat1': 0.36363636363636365, 'radio_tower0': 0.36363636363636365}
highest closeness:
{'boat0': 0.45454545454545453}
highest betweeness:
{'boat0': 0.46060606060606063}
ser at båt 0 skårer høyest på alle kategorier
Removed node boat0 using closeness_centrality
- Resultat etter angrep 3 -
highest degree:
{'boat1': 0.30000000000000004, 'boat2': 0.30000000000000004, 'boat3': 0.30000000000000004, 'boat6': 0.30000000000000004, 'radio_tower0': 0.30000000000000004}
highest closeness:
{'boat1': 0.32000000000000006, 'boat2': 0.32000000000000006, 'boat3': 0.32000000000000006, 'boat6': 0.32000000000000006, 'radio_tower0': 0.32000000000000006}
highest betweeness:
{'boat6': 0.11111111111111112}
- Random angrep -
highest degree:
{'boat4': 0.41666666666666663, 'radio_tower0': 0.41666666666666663}
highest closeness:
{'boat4': 0.5041666666666667}
highest betweeness:
{'boat6': 0.2840909090909091}
Prøv å evaluere angrepene som du har gjort nå med metoder fra tidligere seksjoner.
# Din kode her
For å videre evaluere angrepene vil vi introdusere "noder i største partisjon" som mål. Beregn størrelsen av største partisjon og sammenlign tilfeldig angrep med målrettet ved tre noder fjernet.
print("calculated attack:",attackVDES3.get_largest_components_size())
print("random attack:",attackVDESrandom.get_largest_components_size())
print("\nVi kan her se at random attack ikke klarte å gjøre noen noder utilgjenglig for hverandre (utenom de som er fjernet).")
print("Sammenlignet med target attack hvor vi delte grafen i to, samtidig som vi gjorde boat9 utilgjengelig ved å fjerne satal0ite1")
print("Skadene er derfor utrolig forskjellig")
calculated attack: 5 random attack: 11 Vi kan her se at random attack ikke klarte å gjøre noen noder utilgjenglig for hverandre (utenom de som er fjernet). Sammenlignet med target attack hvor vi delte grafen i to, samtidig som vi gjorde boat9 utilgjengelig ved å fjerne satal0ite1 Skadene er derfor utrolig forskjellig
Diskuter fordeler og ulemper med noder i største partisjon som pålitelighetsmål. Er dette et fornuftig mål i vårt tilfelle?
Drøft kort viktigheten av informasjonen rundt en nettverkstopologi.
Legg til tre kanter for å sikre flest mulig noder mot angrep. Diskuter så hvorfor du la til de kantene du gjorde og om det nå er mer robust mot angrep.
# En bug gjør at jeg må fjerne kantene jeg legger til, men de viser fortsatt feil verdier
# VDES2.remove_edge("boat9","boat8")
# VDES2.remove_edge("boat7","boat5")
# VDES2.remove_edge("boat9","satilite0")
VDES2 = VDES
def findMinDegreeVDES():
minDegree = {}
degreeVDES = VDES2.degree_centrality()
v2 = min(degreeVDES.items(), key=operator.itemgetter(1))[1]
for x in degreeVDES:
if degreeVDES[x] == v2:
minDegree[x] = degreeVDES[x]
print("lowest degree:\n",minDegree)
# kant 1
print("\n- adding edge 1 -")
findMinDegreeVDES()
VDES2.add_edge("boat9","boat8")
print("Adding edge between boat9 and boat8")
# kant 2
print("\n- adding edge 2 -")
findMinDegreeVDES()
VDES.add_edge("boat7","boat5")
print("Adding edge between boat7 and boat5")
# kant 3
print("\n- adding edge 3 -")
findMinDegreeVDES()
VDES.add_edge("boat9","satilite0")
print("Adding edge between boat9 and satilite0")
print("\nGrunnen til at jeg har lagt til disse kantene er for å gjøre noder med lav degree mer robuste. \nI tilegg hvis flere noder har samme degree kobler jeg til noden lengst unna, slik at Shortest path \n(closenness og betweenness øker) og omveien ikke blir så stor.")
- adding edge 1 -
lowest degree:
{'boat9': 0.07692307692307693}
Adding edge between boat9 and boat8
- adding edge 2 -
lowest degree:
{'boat7': 0.15384615384615385, 'boat9': 0.15384615384615385}
Adding edge between boat7 and boat5
- adding edge 3 -
lowest degree:
{'boat9': 0.15384615384615385}
Adding edge between boat9 and satilite0
Grunnen til at jeg har lagt til disse kantene er for å gjøre noder med lav degree mer robuste.
I tilegg hvis flere noder har samme degree kobler jeg til noden lengst unna, slik at Shortest path
(closenness og betweenness øker) og omveien ikke blir så stor.
Antall noder i største partisjon er et eksempel på et mål for hvor mye av et nettverk som har overlevd. Plott et linjediagram (en graf) med antall noder i største komponent langs y_aksen, antall noder fjernet på x_aksen og fjern en etter en node med de 4 forskjellige angrepene.
Lag en funksjon for denne grafen.
Bruk ConstructedGraph nettverket og plott grafen.
def allFourAttacks(graph):
nodes = graph.number_of_nodes()
# 4 forskjellige angrep
graphs = [graph, graph, graph, graph]
values = [[0 for _ in range(nodes)] for _ in graphs]
# angriper grafen med forskjellig angrep.
for attackType in range(0,nodes-1):
graphs[0] = graphs[0].delete_nodes_attack(n=1, centrality_index="closeness", print_result=False)
graphs[1] = graphs[1].delete_nodes_attack(n=1, centrality_index="degree", print_result=False)
graphs[2] = graphs[2].delete_nodes_attack(n=1, centrality_index="betweenness", print_result=False)
graphs[3] = graphs[3].delete_random_nodes(1, print_result=False)
# finne største komponenet for vært angrep
for number, graph in enumerate(graphs):
values[number][attackType] = graphs[number].get_largest_components_size()
plt.xlabel("attacks")
plt.ylabel("component size")
# legge til i grafen
for z in range(4):
plt.plot(values[z])
allFourAttacks(ConstructedGraph(expanded=False))
Er noen av angrepene bedre enn andre? Hvordan gjør tilfeldige feil det?
Kostnaden kan måles med antall kanter per node i nettverket. Beregn kanter per node for VDES med ekstra kanter og VDES uten.
# Hadde problemer med noen bugs, lager derfor VDES på nytt
VDES3 = VDESGraph()
print("- Uten ekstra kanter -")
for node in VDES3:
print(node,":",len(VDES3.edges(node)))
print("\n- Med ekstra kanter -")
for node in VDES2:
print(node,":",len(VDES2.edges(node)))
- Uten ekstra kanter - boat0 : 5 boat1 : 4 boat2 : 3 boat3 : 5 boat4 : 5 boat5 : 3 boat6 : 3 boat7 : 2 boat8 : 2 boat9 : 1 satilite0 : 3 satilite1 : 5 radio_tower0 : 5 radio_tower1 : 4 - Med ekstra kanter - boat0 : 5 boat1 : 4 boat2 : 3 boat3 : 5 boat4 : 5 boat5 : 4 boat6 : 3 boat7 : 3 boat8 : 3 boat9 : 3 satilite0 : 4 satilite1 : 5 radio_tower0 : 5 radio_tower1 : 4
print("Orginal VDES")
VDES3.draw()
print("VDES med ekstra kanter")
VDES2.draw()
Orginal VDES
VDES med ekstra kanter
Diskuter hvor mye burde man sikre et nettverk med hensyn på redundans?